package com.atcumt.Carl.Stack;

import java.util.*;

// 单调栈:
// 一维数组，要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置
public class Stack03 {

    /**
     * 每日温度
     */
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] res = new int[n];
        Deque<Integer> stack = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            // 栈非空 && 当日气温 > 栈顶气温
            while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
                res[stack.peek()] = i - stack.peek(); // 计算天数的差值
                stack.pop();
            }
            stack.push(i); // 当日气温 <= 栈顶气温, 直接入栈
        }
        return res;
    }

    /**
     * 下一个更大元素
     * nums1 数字的下一个更大元素:在 nums2 中对应位置右侧的第一个比 x 大的元素
     */
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Deque<Integer> stack = new LinkedList<>();
        Map<Integer, Integer> map = new HashMap<>();
        int[] res = new int[nums1.length];
        for (int i = 0; i < nums2.length; i++) {
            // 栈非空 && nums2[i] > 栈顶数字(nums1中)。下标存入 res 数组
            while (!stack.isEmpty() && nums2[i] > nums2[stack.peek()]) {
                map.put(nums2[stack.pop()], nums2[i]);
            }
            stack.push(i);
        }
        for (int i = 0; i < nums1.length; i++) {
            res[i] = map.getOrDefault(nums1[i], -1);
        }
        return res;
    }

    /**
     * 下一个更大元素Ⅱ
     * 循环数组：在遍历的过程中模拟走两遍 nums，用i % nums.size()操作
     */
    public int[] nextGreaterElements(int[] nums) {
        int n = nums.length;
        Deque<Integer> stack = new LinkedList<>();
        int[] res = new int[n];
        Arrays.fill(res, -1); // 默认值为-1
        for (int i = 0; i < 2 * n; i++) {
            // 栈非空 && 当前数字 (循环数组) > 栈顶数字
            while (!stack.isEmpty() && nums[i % n] > nums[stack.peek()]) {
                res[stack.peek()] = nums[i % n];
                stack.pop();
            }
            stack.push(i % n);
        }
        return res;
    }


}
